package DoExercise.HSP_ZCY.A008_树.A001_普通二叉树.二叉树递归套路_找可能性;

import java.util.ArrayList;
import java.util.List;

public class Code09_派对的最大快乐值
{
    
    public static class Employee
    {
        public int happy;
        public List<Employee> nexts;
        
        public Employee(int h)
        {
            happy = h;//员工的快乐值
            nexts = new ArrayList<>();//员工的直接下级
        }
    }
    
    public static int maxHappy1(Employee boss)
    {
        if (boss == null)
        {
            return 0;
        }
        return process1(boss, false);
    }
    
    public static int process1(Employee cur, boolean up)
    {
        if (up)
        {
            int ans = 0;
            for (Employee next : cur.nexts)
            {
                ans += process1(next, false);
            }
            return ans;
        } else
        {
            int p1 = cur.happy;
            int p2 = 0;
            for (Employee next : cur.nexts)
            {
                p1 += process1(next, true);
                p2 += process1(next, false);
            }
            return Math.max(p1, p2);
        }
    }
    
    public static int maxHappy2(Employee boss)
    {
        if (boss == null)
        {
            return 0;
        }
        Info all = process2(boss);
        return Math.max(all.yes, all.no);
    }
    
    public static class Info
    {
        public int yes;//头节点在来的情况下整棵树的最大快乐值
        public int no;//头节点在不来的情况下整棵树的最大快乐值
        
        public Info(int y, int n)
        {
            yes = y;
            no = n;
        }
    }
    
    public static Info process2(Employee x)
    {
        if (x.nexts.isEmpty())
        {
            return new Info(x.happy, 0);
        }
        int yes = x.happy;
        int no = 0;
        //累加x的所有下属整棵树的最大快乐值
        for (Employee next : x.nexts)
        {
            Info nextInfo = process2(next);
            yes += nextInfo.no;
            no += Math.max(nextInfo.yes, nextInfo.no);
        }
        return new Info(yes, no);
    }
    
    // for test
    public static Employee genarateBoss(int maxLevel, int maxNexts, int maxHappy)
    {
        if (Math.random() < 0.02)
        {
            return null;
        }
        Employee boss = new Employee((int) (Math.random() * (maxHappy + 1)));
        genarateNexts(boss, 1, maxLevel, maxNexts, maxHappy);
        return boss;
    }
    
    // for test
    public static void genarateNexts(Employee e, int level, int maxLevel, int maxNexts, int maxHappy)
    {
        if (level > maxLevel)
        {
            return;
        }
        int nextsSize = (int) (Math.random() * (maxNexts + 1));
        for (int i = 0; i < nextsSize; i++)
        {
            Employee next = new Employee((int) (Math.random() * (maxHappy + 1)));
            e.nexts.add(next);
            genarateNexts(next, level + 1, maxLevel, maxNexts, maxHappy);
        }
    }
    
    public static void main(String[] args)
    {
        int maxLevel = 4;
        int maxNexts = 7;
        int maxHappy = 100;
        int testTimes = 100000;
        for (int i = 0; i < testTimes; i++)
        {
            Employee boss = genarateBoss(maxLevel, maxNexts, maxHappy);
            if (maxHappy1(boss) != maxHappy2(boss))
            {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }
    
}
